package 力扣日常刷题.木22一月.第03天0110;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author 帅小伙
 * @date 2022/1/10
 * @description    https://leetcode-cn.com/problems/all-paths-from-source-to-target/
 */
public class Demo05回溯中等所有可能的路径 {

    List<List<Integer>> ans = new ArrayList<>();
    Deque stack = new ArrayDeque<Integer>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        stack.addLast(0);
        dfs(graph,0,graph.length-1);
        return ans;
    }

    void dfs(int[][] graph,int index,int n) {
        if(index == n){
            ans.add(new ArrayList<>(stack));
            return ;
        }
        for (int i : graph[index]) {
            stack.addLast(i);
            dfs(graph,i,n);
            stack.pollLast();
        }
    }


}
